package sort;

import java.util.Arrays;

/**
 * 工作原理：采用分治法（Divide and Conquer）的一个非常典型的应用
 * 平均 O(nlogn)
 * 最好 O(nlogn)
 * 最坏 O(nlogn)
 * 空间 O(n)
 * 排序方式 Out-place
 * 稳定性 稳定
 */
public class Merge {
    private int [] a = {1,6,2,4,1,5,9};

    private void sort(){
        a = mergeSort(a, 0, a.length - 1);
    }

    private int [] mergeSort(int [] a, int l, int r){
        if (r - l + 1 < 2) {
            int [] x = new int[r - l + 1];
            for(int q = 0;q < r - l + 1;q ++){
                x[q] = a[l + q];
            }
            return x;
        }
        int mid = (l + r)/2;
        return merge(mergeSort(a, l, mid), mergeSort(a, mid + 1, r));
    }


    private int [] merge(int [] left, int [] right){
        int [] res = new int[left.length + right.length];
        for(int i=0,j=0,k=0;k< res.length;k++){
            if (i >= left.length){
                res[k] = right[j++];
            } else if (j >= right.length){
                res[k] =left[i++];
            } else if (left[i] > right[j]){
                res[k] = right[j++];
            } else {
                res[k] = left[i ++];
            }
        }
        return res;
    }

    private void print(){
        System.out.println(Arrays.toString(a));
    }

    public static void main(String [] args){
        Merge maoPao = new Merge();
        maoPao.print();
        maoPao.sort();
        maoPao.print();
    }
}
